In a Public Key Cryptosystem, each user is assigned or chooses a matching pair of keys (P.sub.X, S.sub.X), where P.sub.X is the public key corresponding to the pair and S.sub.X is the secret key. For authentication purposes, the public key for each user is catalogued and/or certified by a central authority (or authorities) so that other users in the system can retrieve the authentic public key for any individual. Public Key Cryptosystems can be used for many purposes, including encryption and/or digital signatures.
One problem with a PKC (and Cryptosystems in general) is that they may be abused by non-law-abiding users. For example, two criminals could communicate using a PKC established by the Government and an authority would have no way to decrypt their message traffic, even if the authority had received a court authorization to wiretap the communication. Such activity might take place even if the PKC were established solely for the purposes of digital signatures since the criminals might use the PKC for other purposes such as encryption.
This problem has been addressed in a series of papers. Blakley [1] and Shamir [6] describe methods wherein the secret cryptographic key of each user is shared among one or more trustees. (Trustees are presumably few in number and are highly trusted entities.) In particular, each trustee is given a secret piece of the secret key for each user. The sharing of a key needs to satisfy 2 properties. First, no subset of k trustees should be able to pool their knowledge in order to figure out the secret key of a user. Second, any set of h&gt;k trustees should be able to recover the secret key of a user by pooling their shares of that key. Many such "secret sharing" schemes are known in the literature (e.g., see the survey paper by Simmons [7]). In such a scheme, the user is assured that the authorities cannot learn his or her secret key without the approval of at least k+1 trustees, and the authorities are assured that they can obtain the secret key of any individual with the approval of any h trustees. Variations of these schemes are known which can also handle trustees who work in cooperation with the criminals, provided that the number of such malicious trustees is not too large.
One difficulty with the secret sharing schemes is that there is no provision for insuring that the trustees have received valid shares for each user's secret key. Indeed, when the trustees reveal their shares under a court order (say), the shares may be found to be useless because the criminal user did not provide proper shares of his or her secret key. This problem is resolved in [2], where it is shown how shares can be provided in a way so that each trustee can be assured that he or she has received a valid share of the secret key. A user who does not provide valid shares for their secret key can then be identified and excluded from the system.
A secret sharing scheme in which each trustee can be assured that he or she has a valid share of a secret is known as a Verifiable Secret Sharing (VSS) scheme. Many such schemes are known in the literature. In [5], Micali claims that a VSS scheme used in this fashion forms what he calls a Fair Public--Key Cryptosystem. Although the precise definition of a Fair PKC is not provided, Micali states that a key property of a Fair PKC is that it "cannot be misused by criminal organizations" [5]. As demonstrated by the Killian attack, however, it is clear that the Micali method for Fair PKCs can be seriously misused by criminals.
The flaw in the Micali method is derived from the fact that it is possible for a user X to choose a pair of keys (S.sub.X, P.sub.X) with the special properties that:
1) the trustees can be provided with valid shares of the secret key S.sub.X, and
2) the public key P.sub.X can be easily converted into a second public key P'.sub.X (using a published algorithm) for a second cryptosystem for which the user has also precomputed a second secret key S'.sub.X.
The criminal user can then communicate using the second cryptosystem and the second pair of keys. The central authority (with the aide of the trustees) can retrieve S.sub.X but this will not be useful in deciphering traffic encrypted with S'.sub.X. Moreover, the central authority may have no hope of discovering S'.sub.X.
This problem can be resolved by having the trustees themselves select the pair of keys for each user, as suggested in [4]. But schemes in which the trustees select the secret key for each user may leave the user with no assurance that his key has been properly generated (so as to be secure). Such a scheme would not satisfy Property 1.
It would be desirable to have a method for the selection of key pairs for individuals that protects the privacy and security concerns of law-abiding users as well as the security concerns of the central authority. That is the subject of this paper.